CF999E Reachability from the Capital

显然,在一个强联通分量中,只要有一个城市与ss联通,那么整个分量就与ss联通。

于是我们可以缩点,统计它的入度。如果入度为00,我们就从ss向这个缩点连一条边,如果入度不为0,说明其他城市可以到达它,我们就不需要单独连边。

最后,注意特判与ss在同一强联通分量的点。

#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

const int MAXN = 5000;
int n , m , s , u , v;
vector< int > Graph[ MAXN + 5 ];

int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int bel[ MAXN + 5 ] , In[ MAXN + 5 ];
bool is[ MAXN + 5 ];
stack< int > S;
void Tarjan( int u ) {
	dfn[ u ] = low[ u ] = ++ depth;
	S.push( u ) , is[ u ] = 1;
	
	int v;
	for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
		v = Graph[ u ][ i ];
		if( !dfn[ v ] ) {
			Tarjan( v );
			low[ u ] = min( low[ u ] , low[ v ] );
		}
		else if( is[ v ] )
			low[ u ] = min( low[ u ] , dfn[ v ] );
	}
	if( dfn[ u ] == low[ u ] ) {
		++ cnt;
		do{
			v = S.top( );
			S.pop( ); is[ v ] = 0;
			bel[ v ] = cnt;
		}while( u != v );
	}
}

int main( ) {
	scanf("%d %d %d",&n,&m,&s);
	for( int i = 1 ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v);
		Graph[ u ].push_back( v );
	}
	for( int i = 1 ; i <= n ; i ++ )
		if( !dfn[ i ] ) Tarjan( i );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
			int u = bel[ i ] , v = bel[ Graph[ i ][ j ] ];
			if( u != v ) In[ v ] ++;
		}
	int Ans = 0;
	for( int i = 1 ; i <= cnt ; i ++ )
		if( !In[ i ] && i != bel[ s ] ) Ans ++;
	printf("%d\n",Ans);
	return 0;
}